#include <iostream>
#include "sort.h"
#include <vector>
#include <functional>
#include <ctime>
using namespace std;

 const int n=1000*1000;
 const int m=1000*100;
//有序度1%
const int k1= 1000*100;
const int h1=1000*10;
//有序度10%
const int k2=316227;
const int h2=31622;
//有序度90%
const int k3= 683772;
const int h3= 68377;
//有序度99%
const int k4= 9000*100;
const int h4= 9000*10;

void test1(vector<int> &arr1)
{
  vector<int> a =arr1;
  vector<int> b =arr1;
    clock_t st1=clock();
    heapsort(arr1);
    clock_t end1 = clock();
    cout<<"heapsort 1%运行时间" <<(double)(end1-st1)/CLOCKS_PER_SEC<<"秒" << endl;

    
    clock_t st2=clock();
    quicksort(a);
    clock_t end2 = clock();
    cout<<"quicksort 1%运行时间" <<(double)(end2-st2)/CLOCKS_PER_SEC<<"秒" << endl;

    clock_t st3=clock();
    Newquicksort(b);
    clock_t end3 = clock();
    cout<<"Newquicksort 1%运行时间" <<(double)(end3-st3)/CLOCKS_PER_SEC<<"秒" << endl;
}


void test2(vector<int> &arr2)
{
  vector<int> a =arr2;
  vector<int> b =arr2;
    clock_t st1=clock();
    heapsort(arr2);
    clock_t end1 = clock();
    cout<<"heapsort 10%运行时间" <<(double)(end1-st1)/CLOCKS_PER_SEC<<"秒" << endl;

    
    clock_t st2=clock();
    quicksort(a);
    clock_t end2 = clock();
    cout<<"quicksort 10%运行时间" <<(double)(end2-st2)/CLOCKS_PER_SEC<<"秒" << endl;

    clock_t st3=clock();
    quicksort(b);
    clock_t end3 = clock();
    cout<<"Newquicksort 10%运行时间" <<(double)(end3-st3)/CLOCKS_PER_SEC<<"秒" << endl;
}

void test3(vector<int> &arr3)
{vector<int> a =arr3;
vector<int> b =arr3;
    clock_t st1=clock();
    heapsort(arr3);
    clock_t end1 = clock();
    cout<<"heapsort 90%运行时间" <<(double)(end1-st1)/CLOCKS_PER_SEC<<"秒" << endl;

    
    clock_t st2=clock();
    quicksort(a);
    clock_t end2 = clock();
    cout<<"quicksort 90%运行时间" <<(double)(end2-st2)/CLOCKS_PER_SEC<<"秒" << endl;

        clock_t st3=clock();
    quicksort(b);
    clock_t end3 = clock();
    cout<<"Newquicksort 90%运行时间" <<(double)(end3-st3)/CLOCKS_PER_SEC<<"秒" << endl;
}


void test4(vector<int> &arr4)
{vector<int> a =arr4;
vector<int> b =arr4;
    clock_t st1=clock();
    heapsort(arr4);
    clock_t end1 = clock();
    cout<<"heapsort 99%运行时间" <<(double)(end1-st1)/CLOCKS_PER_SEC<<"秒" << endl;

    
    clock_t st2=clock();
    quicksort(a);
    clock_t end2 = clock();
    cout<<"quicksort 99%运行时间" <<(double)(end2-st2)/CLOCKS_PER_SEC<<"秒" << endl;

        clock_t st3=clock();
    quicksort(b);
    clock_t end3 = clock();
    cout<<"Newquicksort 99%运行时间" <<(double)(end3-st3)/CLOCKS_PER_SEC<<"秒" << endl;
}


void test5(vector<int> &brr1)
{vector<int> b =brr1;
    clock_t st1=clock();
    heapsort(brr1);
    clock_t end1 = clock();
    cout<<"heapsort 1%运行时间" <<(double)(end1-st1)/CLOCKS_PER_SEC<<"秒" << endl;

    
    clock_t st2=clock();
    quicksort(b);
    clock_t end2 = clock();
    cout<<"quicksort 1%运行时间" <<(double)(end2-st2)/CLOCKS_PER_SEC<<"秒" << endl;
}

void test6(vector<int> &brr2)
{vector<int> b =brr2;
    clock_t st1=clock();
    heapsort(brr2);
    clock_t end1 = clock();
    cout<<"heapsort 10%运行时间" <<(double)(end1-st1)/CLOCKS_PER_SEC<<"秒" << endl;

    
    clock_t st2=clock();
    quicksort(b);
    clock_t end2 = clock();
    cout<<"quicksort 10%运行时间" <<(double)(end2-st2)/CLOCKS_PER_SEC<<"秒" << endl;
}

void test7(vector<int> &brr3)
{   vector<int> b =brr3;
    clock_t st1=clock();
    heapsort(brr3);
    clock_t end1 = clock();
    cout<<"heapsort 90%运行时间" <<(double)(end1-st1)/CLOCKS_PER_SEC<<"秒" << endl;

 
    clock_t st2=clock();
    quicksort(b);
    clock_t end2 = clock();
    cout<<"quicksort 90%运行时间" <<(double)(end2-st2)/CLOCKS_PER_SEC<<"秒" << endl;
}


void test8(vector<int> &brr4)
{    vector<int> b =brr4;
    clock_t st1=clock();
    heapsort(brr4);
    clock_t end1 = clock();
    cout<<"heapsort 99%运行时间" <<(double)(end1-st1)/CLOCKS_PER_SEC<<"秒" << endl;


    clock_t st2=clock();
    quicksort(b);
    clock_t end2 = clock();
    cout<<"quicksort 99%运行时间" <<(double)(end2-st2)/CLOCKS_PER_SEC<<"秒" << endl;
}



int main(){
  
   vector<int> arr;
  for(int p=1;p<n;p++)
    {
      arr.push_back(p);
    }
  vector<int> arr1=arr;
  vector<int> arr2=arr;
  vector<int> arr3=arr;
  vector<int> arr4=arr;

int begin1 = (rand() % (n-k1));
  for (int i1 = begin1; i1 < begin1+k1; i1++)
    { std::swap( arr1[ i1 ], arr1[ begin1+k1-i1 ] );  };
    
  int begin2 = (rand() % (n-k2));
  for (int i2 = begin2; i2 < begin2+k2; i2++)
    { std::swap( arr2[ i2 ], arr2[ begin2+k2-i2 ] );  };
    
  int begin3 = (rand() % (n-k3));
  for (int i3 = begin3; i3 < begin3+k3; i3++)
    { std::swap( arr3[ i3 ], arr3[ begin3+k3-i3 ] );  };
    
  int begin4 = (rand() % (n-k4));
  for (int i4 = begin4; i4 < begin4+k4; i4++)
    { std::swap( arr4[ i4 ], arr4[ begin4+k4-i4 ] );  }; 







  vector<int> brr;
  for(int q=1;q<m;q++)
    {
      brr.push_back(q);
    }

  vector<int> brr1=brr;
  vector<int> brr2=brr;
  vector<int> brr3=brr;
  vector<int> brr4=brr;
  


  int beg1 = (rand() % (m-h1));
  for (int j1 = beg1; j1 < beg1+h1; j1++)
    { std::swap( arr1[ j1 ], arr1[ beg1+h1-j1 ] );  };
    
  int beg2 = (rand() % (m-h2));
  for (int j2 = beg2; j2 < beg2+h2; j2++)
    { std::swap( arr2[ j2 ], arr2[ beg2+h2-j2 ] );  };
    
  int beg3 = (rand() % (m-h3));
  for (int j3 = beg3; j3 < beg3+h3; j3++)
    { std::swap( arr3[ j3 ], arr3[ beg3+h3-j3 ] );  };
    
  int beg4 = (rand() % (m-h4));
  for (int j4 = beg4; j4 < beg4+h4; j4++)
    { std::swap( arr4[ j4 ], arr4[ beg4+h4-j4 ] );  }; 
    


    test1(arr1);
    test2(arr2);
    test3(arr3);
    test4(arr4);
    //  test5(brr1);
    //  test6(brr2);
    //  test7(brr3);
    //  test8(brr4);
}

